#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,a,b) for(register int i = (a);i <= (b);++i)
#define per(i,a,b) for(register int i = (a);i >= (b);--i) 
#define mkp std::make_pair
typedef long long ll;
typedef unsigned long long ull;
using std::string;using std::cin;using std::cout;
inline bool cmp(int x,int y){return x < y;}

const int N = 1e6+9;
const int inf = 1e9+9;
const double eps = 1e-7;
const int p = 100003;
int _,n,m,a[2*N],u,v,dis[2*N],cnt[2*N];
bool flag[2*N];

std::queue<int> q;
int head[2*N],next[2*N],ver[2*N],tot;
inline void link(int x,int y){ver[++tot] = y , next[tot] = head[x] , head[x] = tot;}

inline void spfa(int root){
    while(q.size()) q.pop();
    q.push(root); flag[root] = true;
    dis[root] = 0 , cnt[root] = 1;
    while(q.size()){
        u = q.front(); q.pop();
        flag[v] = false;
        for(int i = head[u];i;i = next[i]){
                v = ver[i];
                if(dis[v] == dis[u]+1) cnt[v] += cnt[u] , cnt[v] %= p;
                if(dis[v] > dis[u]+1){dis[v] = dis[u]+1 , cnt[v] = cnt[u] , flag[v] = true;q.push(v);}
                // std::cerr << u << " -> " << v << "\n";
                // std::cerr << "u = " << u << " " << dis[u] << " " << cnt[u] << "\n";
                // std::cerr << "v = " << v << " " << dis[v] << " " << cnt[v] << "\n";
        }
    }
}

int main(){
    std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef LOCAL //use "g++ xxx.cpp -DLOCAL"
        freopen("in.in", "r", stdin);
    #endif
    cin >> n >> m;
    std::memset(dis,inf,sizeof(dis));
    rep(i,1,m){cin >> u >> v;link(u,v),link(v,u);}
    spfa(1);
    rep(i,1,n) cout << cnt[i]%p << "\n";
    return 0;
}